package mo.leetcode_top;

import java.util.*;

public class L210 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> res = new ArrayList<>();
        ArrayList[] graph = new ArrayList[numCourses];
        int[] in = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int[] preRequire = prerequisites[i];
            ArrayList<Integer> targets = graph[preRequire[1]];
            if (Objects.isNull(targets)) {
                targets = new ArrayList<>();
                graph[preRequire[1]] = targets;
            }
            targets.add(preRequire[0]);
            in[preRequire[0]]++;
        }

        Stack<Integer> candidates = new Stack<>();
        for (int i = 0; i < in.length; i++) {
            if (in[i] == 0) {
                candidates.push(i);
            }
        }

        while (!candidates.isEmpty()) {
            Integer candidate = candidates.pop();
            res.add(candidate);
            if (Objects.nonNull(graph[candidate])) {
                for (int i = 0; i < graph[candidate].size(); i++) {
                    Integer index = (Integer) graph[candidate].get(i);
                    in[index]--;
                    if (in[index] == 0) {
                        candidates.push(index);
                    }
                }
            }
        }

        if (res.size() == numCourses) {
            int[] converts = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                converts[i] = res.get(i);
            }
            return converts;
        } else {
            return new int[0];
        }
    }

    public static void main(String[] args) {
        L210 test = new L210();
        System.out.println(Arrays.toString(test.findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
    }

}
